package QuestionDaily;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;

public class sumSubarrayMins_907 {
    /**
     * 找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
     * 由于答案可能很大，因此 返回答案模 10^9 + 7 。
     */
    int MOD = (int)1e9+7;

    public int sumSubarrayMins(int[] arr) {
        /**
         * 维护每个不断向后伸长的子串的最小值
         * 超时了
         * 只能通过78/87个数据
         */
        long  ans=0;
        for (int i = 0; i < arr.length; i++) { //arr[i]开始的子串
            // 初始化minNum
            int min = arr[i];
            for(int t=i;t<arr.length;t++){  //arr中从i为 开始，结尾从i 到 t的子串集合
                if (arr[t] < min)
                    min = arr[t];
                //可以直接计算以每一位为起点的子串集合
                ans+=min;
                ans%=MOD;
            }
        }
        return (int) ans;
    }

    /**
     * 高解单调栈写法
     */
    public int sumSubarrayMins2(int[] arr) {
        /**
         * 算法重点1
         * 计算以 arr[i] 为最小值的子数组的个数 n
         * 那么arr[i] 对答案ans的贡献值就是 n*arr[i]
         * 算法重点2
         * 可以从arr[i]向左和右寻找比小于等于它（避免重复统计）的元素然后停止
         * 以 arr[i] 为最小值的子数组的个数为 (i−L)⋅(R−i)，对答案的贡献为 arr[i]⋅(i−L)⋅(R−i)
         * 算法重点3
         * 高效计算边界
         * 使用栈，移除栈中 ≥arr[i]的元素后，栈顶的下标就是 arr[i] 的左边界
         * 如果此时栈为空，那么左边界为 −1。
         */
        long ans = 0;
        Deque<Integer> st = new ArrayDeque<>();
        st.push(-1); // 哨兵
        for (int r = 0; r <= arr.length; ++r) {
            int x = r < arr.length ? arr[r] : -1; // 假设 arr 末尾有个 -1
            while (st.size() > 1 && arr[st.peek()] >= x) {
                //栈顶元素大于等于当前元素时，要将前面大于等于当前元素的数都出栈并且计算他们各自贡献值
                //维持单调增栈
                int i = st.pop();
                //直接在出栈的时候计算贡献。
                ans += (long) arr[i] * (i - st.peek()) * (r - i); // 累加贡献
            }
            st.push(r);
        }
        return (int) (ans % MOD);
    }


}
